Increasing Triplet Subsequence

Posted on   |   In   |  

判断LIS的长度是否大于3

Increasing Triplet Subsequence

Increasing Triplet Subsequence
大意:给定序列，找出序列的最长递增子序列的长度是否大于3

常规方法: 求出最长递增自序列的长度，判断是否大于3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        size_t length = nums.size();
        
        int lis = 1;
        
        int LIS[length];
        
        for(int i = 0; i < length; i++){
            LIS[i]  =1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j] && LIS[i] < LIS[j] + 1)
                    LIS[i] = LIS[j] +1;
            }
            if(LIS[i] > lis)
                lis = LIS[i];
        }
        return lis >= 3;
    }
};

O(n)的方法:
建立一个由两个数构成的数组，扫描当前数组:

如果这个数比其中的最小的数要小，就将最小的数更新为当前数；
如果这个数位于两个数的中间，就将最大的数更新为当前数；
否则的话，就找到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int min = INT_MAX;
        int mid = INT_MAX;
        
        for(auto n:nums){
            if(n <= min)
                min = n;
            else if(n <= mid)
                mid = n;
            else
                return true;
        }
    }
};